Number Theory

Number bases

Decimal numbers are written in base 10: .
For an arbitrary base , , where the subscript denotes the base of the number. Binary (base 2) numbers use digits 0 and 1, while hexadecimal (base 16) numbers use digits 0-9 and A-F.

Divisibility

The notation means that divides , or is a factor of , or is a multiple of .

Standard divisibility tests

A number is divisible by 3 if the sum of its digits is divisible by 3.
A number is divisible by 4 if the last 2 digits are divisible by 4.
A number is divisible by 5 if the last digit is divisible by 5.
A number is divisible by 8 if the last 3 digits are divisible by 8.
A number is divisible by 9 if the sum of the digits is divisible by 9.
A number is divisible by 11 if the sum of digits with alternating signs is divisible by 11.

Prime divisibility algorithm

To test a large number for divisibility by prime , let or .
Then, choose an and such . and must be coprime, so then .
Set up iteration , , and iterate until is small enough to easily test for divisibility by .

Division algorithm

The division algorithm (or Euclid's division lemma) states that for any pair of integers and with , can be uniquely expressed as:

Where is the quotient and is the remainder, with .

Modular arithmetic

From the division algorithm, a number can be expressed as , where is the quotient and is the remainder. In modular arithmetic, this can be written as .

Two numbers and are congruent modulo () if they have the same remainder when divided by . Equivalently, and are congruent modulo if their difference is divisible by .

Rules

For and :

: Adding congruent values to both sides works
: Subtracting congruent values to both sides works
: Multiplying congruent values to both sides works
for , : Raising to a power on both sides works
If is a polynomial in with integer coefficients, .
If and and and are coprime,

Note that generally division does not work. But, if , and , then . That is, you can divide by a value coprime to the modulo.

Solving linear congruences

A linear congruence is an equation of the form . It has a solution if and only if , where . There are solutions given by:
Where is a solution found by inspection, and ^[1].

The conditions for solutions are:

If , then the congruence has a unique solution.
If and does not divide , the congruence has no solutions.
If and does divide , there are solutions.

To find a solution :

If or , replace them with their remainder modulo .
To change the sign of either side, both sides can be multiplied by , or multiples of added to either side.
If and have a common factor that is coprime to , this can be cancelled.
If , , and all have a common factor, this can be cancelled (changing the modulo of the congruence). This happens when .
Get the coefficient on to be 1.

Prime numbers

Fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or a unique product of primes.

Euclid's lemma

A pair of integers are coprime if they have no common factors other than 1.
Euclid's lemma states that:

For any integers , if and , then .
Alternatively, if is a prime and , must divide at least one of or .

Integer combinations

An integer combination of integers and is any integer of form for integer values of and . If and , then :

If then for some
If then for some

Because is a factor of and , any integer combination of and is a multiple of . We can now use this result to prove coprimality.

If for some and , then , implying and are coprime if . The converse is also true:

Assume and are coprime.
This means has a unique solution. Suppose this solution is .
. This means for some .
Rearranging, we get for some and . Thus, there is some integer combination of and equal to 1.

These two results give us:
Two integers and are coprime if and only if there are two integers and such that .

The highest common factor of and can be found by finding the smallest possible integer written as ^[2].

Footnote on solving linear congruences
Once you have one solution the rest is fairly simple - the whole thing just means adding multiples of to get the other solutions. Try it out a few times, and take a look at the exercises on Integral.↩︎
Footnote on finding highest common factor using
No proof provided, but its kinda obvious? has to have a factor of , so the smallest (nonnegative, integer) value of is going to be itself.↩︎